﻿//https://leetcode.cn/problems/longest-valid-parentheses/?envType=study-plan-v2&envId=top-100-liked

class Solution {
public:
    int longestValidParentheses(string s)
    {
        int n = s.size();
        vector<int> dp(n);
        int ret = 0;

        for (int i = 1; i < n; i++)
        {
            if (s[i] == ')')
            {
                //当此时有一个完整的括号对 向前判断i-2位置有几个括号对
                if (s[i - 1] == '(')
                {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                }
                //如果是两个连续的右括号 判断前一个右括号（对）的前一个位置是否为左括号
                else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(')
                {
                    //加上跳过的右括号（对）的最长子串
                    //如果越界 前面不可能有左括号与之匹配 只能+0
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                ret = max(ret, dp[i]);
            }

        }

        return ret;

    }
};

//https://leetcode.cn/problems/unique-paths/?envType=study-plan-v2&envId=top-100-liked

class Solution {
public:
    int uniquePaths(int m, int n)
    {
        vector<vector<int>> memo(m + 1, vector<int>(n + 1));

        return dfs(m, n, memo);
    }

    int dfs(int m, int n, vector<vector<int>>& memo)
    {
        //进入函数时先检查
        if (memo[m][n])
        {
            return memo[m][n];
        }

        //递归出口
        if (m == 0 || n == 0) return 0;
        if (m == 1 && n == 1)
        {
            memo[m][n] = 1;
            return 1;
        }

        //函数主体
        memo[m][n] = dfs(m, n - 1, memo) + dfs(m - 1, n, memo);
        return memo[m][n];
    }
};
